#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
int shortestPath(vector<vector<int>>& grid, int k) {
	const int m = grid.size(), n = grid[0].size();
	if (m == 1 && n == 1) 
		return 0;
	int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };
	k = min(k, m + n - 3);
	vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));
	queue<tuple<int, int, int>> q;
	q.push({ 0,0,k });
	visited[0][0][k] = true;
	int step = 0;
	while (!q.empty())
	{
		int sz = q.size();
		step++;
		for (int i = 0; i < sz; i++)
		{
			auto [x1, y1, k1] = q.front();
			q.pop();
			for (int z = 0; z < 4; z++)
			{
				int x2 = x1 + dx[z], y2 = y1 + dy[z];
				if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n)
				{
					if (grid[x2][y2] == 0 && visited[x2][y2][k1] == false)
					{
						if (x2 == m - 1 && y2 == n - 1)
							return step;
						q.push({ x2,y2,k1 });
						visited[x2][y2][k1] = true;
					}
					else if(grid[x2][y2] == 1 && k1 > 0 && visited[x2][y2][k1 - 1] == false)
					{
						q.push({ x2,y2,k1 - 1});
						visited[x2][y2][k1 - 1] = true;
					}
				}
			}
		}
	}
	return -1;
}
int snakesAndLadders(vector<vector<int>>& board) {
	int n = board.size();
	vector<bool> visited(n * n + 1);
	auto Getpos = [&](int id) -> pair<int, int> {
		int row = (id - 1) / n;
		int col = (id - 1) % n;
		if (row % 2 == 1)
			col = n - 1 - col;
		return { n - 1 - row, col };
	};
	queue<int> q;
	q.push(1);
	visited[1] = true;
	int ret = 0;
	while (!q.empty()) {
		int sz = q.size();
		ret++;
		for (int i = 0; i < sz; i++) {
			auto tmp = q.front();
			q.pop();
			for (int k = 1; k <= 6; k++) {
				int next = tmp + k;
				if (next > n * n)
					break;
				auto [x, y] = Getpos(next);
				if (board[x][y] != -1)
					next = board[x][y];
				if (visited[next] == false) {
					if (next == n * n)
						return ret;
					q.push(next);
				}
				visited[next] = true;
			}
		}
	}
	return -1;
}
int main()
{

	vector<vector<int>> board = { {-1, -1, -1, -1, -1, -1},{-1, -1, -1, -1, -1, -1},
		{-1, -1, -1, -1, -1, -1},{-1, 35, -1, -1, 13, -1},{-1, -1, -1, -1, -1, -1},{-1, 15, -1, -1, -1, -1} };
	snakesAndLadders(board);
	return 0;
}